1. Field of the Invention
The present invention generally relates to the field of variable length coding and to the field of digital video data processing. More particularly, the present invention relates to the field of lookup tables that return the length of bits that a variable length decoder can decode from a sequence of encoded data bits.
2. Related Art
Variable length coding provides an efficient technique for data compression. Many data processing fields have implemented variable length coding to compress data for numerous data applications. One type of variable length coding is known as Huffman coding. The concept of variable length coding is based on replacing data values that appear most frequently in a stream of unencoded data with shorter variable length codewords or symbols while data values that appear less frequently are replaced with longer variable length codewords or symbols. The idea being that the overall length of-the stream of encoded data is smaller than the overall length of the stream of unencoded data.
Moreover, the code for any one of the variable length symbols cannot be the prefix of the code for any other variable length symbol. For example, if the code xe2x80x9c011xe2x80x9d is the code for a particular variable length symbol, then no other code for any other variable length symbol can begin with xe2x80x9c011xe2x80x9d. In this way, when a variable length decoder (which recognizes the variable length symbols including the variable length symbol whose code is xe2x80x9c011xe2x80x9d) encounters a xe2x80x9c011xe2x80x9d at the beginning of a stream of encoded data (e.g., 01110010 . . . ), the xe2x80x9c011xe2x80x9d is decoded by the variable length decoder and then decoding continues with the rest of the stream of encoded data (i.e., xe2x80x9c10010 . . . xe2x80x9d)
The field of digital video data processing applies variable length coding in various applications. In particular, digital video data which is formatted as specified in a specification entitled, xe2x80x9cThe Specification of Consumer Use Digital VCR""s using 6.3 mm Magnetic Tapexe2x80x9d, (HD Video Conference, December, 1994), is variable length coded as described in the specification to reduce the space required to store the digital video data. This specification is commonly known as the DV standard. The DV standard is a compressed digital video data and digital audio data recording standard. A DV digital video system uses a xc2xc inch (6.35 mm) metal evaporate tape to record very high quality digital video data. Alternatively, a DV digital video system can record by transmitting to a memory device (e.g., hard drive, RAM, ROM, etc.) very high quality digital video data and digital audio data for storing therein. Both consumers and professionals use DV digital video systems.
To play the digital video data which is formatted according to the DV standard, the DV digital video system includes a DV decoder for processing the digital video data into a format which can be displayed on an electronic display device. Since the DV decoder processes the digital video data in real-time, speed and performance are crucial characteristics of the DV decoder.
A conventional DV decoder utilizes a lookup table which is similar in function to the single symbol length lookup table 100 illustrated in FIG. 1 to process a stream of digital video data. The table 200 of variable length symbols illustrated in FIG. 2. provides the set of variable length symbols 70A-70D used to variable length encode a stream of data bits (e.g., digital video data) specifically for performing a lookup operation with the single symbol length lookup table 100 of FIG. 1. A first variable length symbol 70A has the code xe2x80x9c0xe2x80x9d. A second variable length symbol 70B has the code xe2x80x9c10xe2x80x9d. A third variable length symbol 70C has the code xe2x80x9c110xe2x80x9d. A fourth variable length symbol 70D has the code xe2x80x9c111xe2x80x9d.
The single symbol length lookup table 100 includes a plurality of lookup entries 10 and a plurality of lookup results 20, whereas each lookup entry has a corresponding lookup result. For example, the lookup entry 10D returns the lookup result 20D. The column 50 shows the variable length symbol whose length is indicated by the lookup result 20.
In processing the stream of data bits (variable length encoded), the conventional DV decoder submits a number of data bits from the stream of data bits (variable length encoded) to the single symbol length lookup table 100 as a lookup entry 10A-10H. The single symbol length lookup table 100 returns a lookup result 20A-20H that is the length (in bits) of a single variable length symbol in response to a lookup entry 10A-10H having a sequence of input data bits (variable length encoded) forming one or more consecutive variable length symbols. In other words, the single symbol length lookup table 100 returns the length or number of bits (starting from the beginning of the stream of input data bits submitted as a lookup entry) which correspond to a variable length symbol that can be decoded by a variable length decoder. Hence, the conventional DV decoder can find a particular variable length symbol (e.g., a variable length symbol corresponding to an End of Block (EOB)) in the stream of digital video data (variable length encoded) by using the single symbol length lookup table 100.
For example, if a stream of data bits (variable length encoded) is xe2x80x9c00100 . . . xe2x80x9d (encoded using the table 200 of variable length symbols shown in FIG. 2), the first bit through the third bit are first submitted as the lookup entry value xe2x80x9c001xe2x80x9d, which corresponds to the lookup entry 10B. Specifically, the stream xe2x80x9c00100 . . . xe2x80x9d has a plurality of consecutive variable length symbols which can be identified once the length of each variable length symbol is determined. In response, the single symbol length lookup table 100 returns the lookup result 20B which has the value xe2x80x9c1xe2x80x9d, which indicates that the lookup entry value xe2x80x9c001xe2x80x9d has a variable length symbol and that its length is xe2x80x9c1xe2x80x9d bit, (i.e., the code xe2x80x9c0xe2x80x9d). Therefore, the stream of data bits (variable length encoded) is advanced by one bit.
Thereafter, the second bit through the fourth bit are submitted as the lookup entry value xe2x80x9c010xe2x80x9d, which corresponds to the lookup entry 10C. In response, the single symbol length lookup table 100 returns the lookup result 20C which has the value xe2x80x9c1xe2x80x9d, which indicates that the lookup entry value xe2x80x9c010xe2x80x9d has a variable length symbol and that its length is xe2x80x9c1xe2x80x9d bit, (i.e., the code xe2x80x9c0xe2x80x9d). Therefore, the stream of data bits (variable length encoded) is advanced again by one bit. Thus, the performance of two lookup operations reveals that the beginning of the stream xe2x80x9c00100 . . . xe2x80x9d has a first variable length symbol 70A and another first variable length symbol 70A. The processing of the stream of data bits (variable length encoded) continues in a similar manner.
Unfortunately, the single symbol length lookup table 100 slows down the processing of digital video data in a conventional DV decoder because of the great number of lookup operations performed on the stream of digital video data. This slow down caused by the single symbol length lookup table 100 limits the conventional DV decoder""s ability to process the digital video data in real-time.
A multiple symbol length lookup table is described. The multiple symbol length lookup table includes a plurality of lookup entries and a plurality of lookup results, each lookup entry having a corresponding lookup result. Each lookup entry comprises a particular sequence of input data bits. The input data bits are encoded with a variable length coding. Moreover, the input data bits form one or more consecutive variable length symbols. Each lookup result comprises a total length of the consecutive variable length symbols in the input data bits. In an embodiment, the multiple symbol length lookup table is generated by using a single symbol length lookup table.
In practice, the input data bits are submitted to the multiple symbol length lookup table as a lookup entry. In response, the multiple symbol length lookup table returns a lookup result that is the total length or number of bits in the input data bits that a variable length decoder can decode. The total length is the length of the codes of the consecutive variable length symbols in the input data bits. Therefore, utilization of the multiple symbol length lookup table reduces the number of lookup operations that are performed on a stream of variable length encoded data and speeds up processing of the variable length encoded data, as compared to employing the single symbol length lookup table.
In an embodiment, a memory size of a memory device that stores the multiple symbol length lookup table is used to determine a table size of the multiple symbol length lookup table. Moreover, the table size determines an entry length for each lookup entry. A larger table size increases the speed of processing the variable length encoded data. In an embodiment, the variable length coding is a Huffman coding.
These and other advantages of the present invention will no doubt become apparent to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the drawing figures.
In one embodiment, the present invention includes a method of generating a symbol length lookup table that returns a total length of one or more consecutive variable length symbols in response to a plurality of input data bits forming the one or more consecutive variable length symbols, the method comprising the steps of: a) determining a table size of the symbol length lookup table based on a memory size associated with a memory device for storing therein the symbol length lookup table; b) determining an entry length for each lookup entry of the symbol length lookup table based on the table size, wherein each lookup entry corresponds to a sequence of the plurality of input data bits; and c) determining a lookup result for each lookup entry of the symbol length lookup table by using a second symbol length lookup table that returns a single symbol length of the one or more consecutive variable length symbols in response to the plurality of input data bits forming the one or more consecutive variable length symbols, wherein the lookup result represents the total length, and wherein the table size of the symbol length lookup table is no less than a second table size of the second symbol length lookup table.
In another embodiment, the present invention includes a method of generating a symbol length lookup table that returns a total length of one or more consecutive variable length symbols in response to a plurality of input data bits forming the one or more consecutive variable length symbols, the method comprising the steps of: a) forming a first data set based on a longest symbol length returned by a second symbol length lookup table that returns a single symbol length of the one or more consecutive variable length symbols in response to the plurality of input data bits forming the one or more consecutive variable length symbols; b) forming a second data set by concatenating a lookup entry of the symbol length lookup table with each first data of the first data set, wherein the lookup entry corresponds to a sequence of the plurality of input data bits; c) using the second symbol length lookup table to find a symbol boundary of each variable length symbol of each second data of the second data set, wherein each second data includes a first bit and a last bit; d) determining a length between the first data bit and a last common symbol boundary, wherein the length represents the total length and represents a lookup result corresponding to the lookup entry of the symbol length lookup table; and e) repeating the steps b) to d) for each lookup entry of the symbol length lookup table.